package someTestExcemple.huaweiOd.container.tree;


//华为OD机试 - 生成哈夫曼树（Java 2024 D卷 100分）
//https://blog.csdn.net/guorui_java/article/details/138309915
import java.util.*;
public class GeneratingHuffmanTrees {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //按权值升序
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> o1.value- o2.value);
        for (int i = 0; i < n; i++) {
            int value = sc.nextInt();
            Node node = new Node(value, null, null);
            priorityQueue.add(node);
        }
        sc.close();
        Node root = createdHuffmanTree(priorityQueue);
        //中序遍历输出
        StringBuilder result = new StringBuilder();
        LDRTraver(root,result);
        System.out.println(result);
    }
     public static class Node {
        int value;
        Node leftChild;
        Node rightChild;

        public Node(int value,Node leftChild,Node rightChild) {
            this.value = value;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

    public static Node createdHuffmanTree(PriorityQueue<Node> priorityQueue) {
        while(priorityQueue.size() >= 2) {
            Node node1 = priorityQueue.poll();
            Node node2 = priorityQueue.poll();
            //循环过程中，如果两节点的值一样，node2肯定比node1高，所以按题目要求node1为左子树
            Node parentNode = new Node(node1.value+node2.value,node1,node2);
            priorityQueue.offer(parentNode);
        }
        //最后剩下一个根节点
        return priorityQueue.poll(); //返回最后生成树的根节点
    }

    public static void LDRTraver(Node root,StringBuilder result) {
        if(root == null) {
            return;
        }
        LDRTraver(root.leftChild,result);
        result.append(root.value+" ");
        LDRTraver(root.rightChild,result);
    }
}
